package com.nananren.shiyan6;

import java.util.ArrayList;
import java.util.List;

public class TravellingSalesmanProblem {
    private int[][] distances; // 城市间距离矩阵
    private int numCities; // 城市数量
    private int minDistance = Integer.MAX_VALUE; // 最小总距离
    private List<Integer> bestRoute = new ArrayList<>(); // 最佳路线

    public TravellingSalesmanProblem(int[][] distances) {
        this.distances = distances;
        this.numCities = distances.length;
    }



    //负责查找最小距离的路线
    public void findMinDistanceRoute() {
        // 生成所有可能的城市排列
        List<List<Integer>> permutations = generatePermutations(new ArrayList<>(), 0, numCities - 1);

        // 遍历每个排列，计算总距离
        for (List<Integer> route : permutations) {
            int totalDistance = 0;
            for (int i = 0; i < route.size() - 1; i++) {
                totalDistance += distances[route.get(i)][route.get(i + 1)];
            }
            // 回到起点
            totalDistance += distances[route.get(route.size() - 1)][route.get(0)];

            // 更新最小距离和最佳路线
            if (totalDistance < minDistance) {
                minDistance = totalDistance;
                bestRoute = new ArrayList<>(route);
            }
        }

        System.out.println("Minimum Distance: " + minDistance);
        System.out.println("Best Route: " + bestRoute);
    }


    // 递归函数，用于生成指定范围内的所有可能的排列组合
    // currentRoute: 当前正在构建的路线
    // start: 开始
    // end: 结束
    private List<List<Integer>> generatePermutations(List<Integer> currentRoute, int start, int end) {
        //存储所有的排列组合
        List<List<Integer>> permutations = new ArrayList<>();

        if (start == end) {// 到达了路线的最后一个位置
            // 将起点添加到当前路线中
            currentRoute.add(0);
            permutations.add(new ArrayList<>(currentRoute));// 新列表添加到 permutations 中。
            // 移除起点，以便下次循环(不重复)
            currentRoute.remove(currentRoute.size() - 1);
            return permutations;
        }

        for (int i = start; i <= end; i++) {
            if (!currentRoute.contains(i)) {
                currentRoute.add(i);
                // 因为每次添加一个新的数字后，我们的路线就增长了一点，所以我们递归地调用函数以生成新的路线。
                permutations.addAll(generatePermutations(currentRoute, start + 1, end));
                // 因为每次我们添加一个新的数字后，我们的路线就增长了一点，所以我们递归地调用函数以生成新的路线
                currentRoute.remove(currentRoute.size() - 1);
            }
        }

        // 所有可能的排列组合
        return permutations;
    }
}
